《剑指offer》 16.数值的整数次方

note:快速幂是一个常用经典需要好好掌握的知识点。另外此题中如何处理指数为负数的情况的方法值得总结

题目描述

实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。

示例 1:

1
2
输入:x = 2.00000, n = 10
输出:1024.00000

示例 2:

1
2
输入:x = 2.10000, n = 3
输出:9.26100

示例 3:

1
2
3
输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25

提示:

  • $-100.0 < x < 100.0$
  • $-2^{31} <= n <= 2^{31}-1$
  • $-10^4 <= x^n <= 10^4$

方法 快速幂算法

思路

快速幂的思想在前面几道题也有所记录,其实本质它是一种二分的思想,将复杂度为$O(n)$的循环求余的方法,复杂度精简到了$O(logn)$。

根据二分推导$x^n = x^{n/2}\times x^{n/2}=(x^2)^{n/2}$,我们的指数显然存在两种情况:

  • n为偶数:$x^n = (x^2)^{n//2}$(//表示整除)
  • n为奇数:$x^n=x(x^2)^{n//2}$

据此,我们可以通过循环$x=x^2$操作,每次幂都会从$n$降至$n//2$,直至n变为0;

那我们可以用一个变量存储出现奇数时单独计算多出的一项$x$,从而让我们的循环可以持续进行。

判断奇数偶数的办法可以用求余,也可以用位运算$n\&1$。

此题另外一个有趣的地方在于对于负指数的处理,很简单的解决方法就是将指数转换为$(-1)(-n)$,也就可以将$x^n$转换为$x^{-1}x^{-n}$。

还有一个问题就是由于n的范围在$[-2^{31},2^{31}-1]$。所以存在当$n=-2^{31}$的时候,直接取反会溢出的情况,所以最好将n转换为long long型参与计算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
double myPow(double x, int n) {
if(x==0)
return 0;
long long a = n;
double res = 1;
if(a<0){
x = 1/x;
a = -a;
}

while(a){
if(a%2==1) res = res*x;
x = x*x;
a/=2;
}

return res;
}
};

复杂度分析

  • 时间复杂度$O(logn)$。快速幂的二分思想,让我们的时间复杂度变为$logN$
  • 空间复杂度$O(1)$。